#include <iostream>
using namespace std;
struct TreeNode
{
	int data;
	int position;
	TreeNode* left;
	TreeNode* right;
	TreeNode(){};
	TreeNode(int value,int pos):data(value),position(pos), left(NULL),right(NULL){};
	~TreeNode(){delete left;delete right;left=NULL;right=NULL;};
	
};
class BinarySearchTree
{
private:
	TreeNode* tnode ;
public:
	BinarySearchTree(TreeNode* t):tnode(t){};
	~BinarySearchTree(){delete tnode;};
	void Add(int value,int position,TreeNode* t);
	void Print(TreeNode* tnode); 	//中序

	
};
void BinarySearchTree::Add(int value,int position,TreeNode* t){
	if(t== NULL) {
		TreeNode* root = new TreeNode(value,position);
		t = root;
	}
	else{
		
		if(value < t->data){
			if(t->left == NULL){
				TreeNode* tmp = new TreeNode(value,position);
				t->left = tmp;
			}
			else{
				Add(value,position,t->left);
			}
			
		}
		else{
			if(t->right == NULL){
				TreeNode* tmp = new TreeNode(value,position);
				t->right = tmp;
			}
			else{
				Add(value,position,t->right);
			}
			
		}
	}
}
void BinarySearchTree::Print(TreeNode* tnode){
	if(tnode){	//if不是while
		Print(tnode->left);
		cout<<tnode->data<<endl;
		Print(tnode->right);
		
	}
}

int Search(TreeNode* t,int target){
	if( t == NULL){
		return -1;
	} 
	else if(t->data == target){
		return t->position;
	}
	else if( t->data > target){
		return Search(t->left,target);
	}
	else{
		return Search(t->right,target);	
	}
}
int main(int argc, char const *argv[])
{
	int arr[5] = {3,6,4,2,0};
	TreeNode* root = NULL;
	BinarySearchTree* bst  = NULL;
	for(int i = 0;i < 5;i++){
		if(i == 0){
			root = new TreeNode(arr[0],i);
		}
		else{
			bst->Add(arr[i],i,root);
		}
	}
	bst->Print(root);
	cout<<Search(root,0)<<endl;
	return 0;
}
 
